package com.leetcode;

import java.util.*;

/**
 * 398. 随机数索引
 * 哈希表 + List
 * 2022-04-25 每日一题
 *
 * @author fy
 * @date 2022/4/25 13:52
 */
public class Solution398 {

    class Solution {

        private Map<Integer, List<Integer>> map;
        private Random random;

        public Solution(int[] nums) {
            // map存储对应的数值, 对应数值的下标放到list中
            map = new HashMap<>();
            random = new Random();
            for (int i = 0; i < nums.length; i++) {
                int num = nums[i];
                List<Integer> list = map.getOrDefault(num, new ArrayList<>());
                list.add(i);
                map.put(num, list);
            }
        }

        public int pick(int target) {
            List<Integer> list = map.get(target);
            if (list == null || list.size() == 0) {
                return -1;
            }
            int index = random.nextInt(list.size());
            return list.get(index);
        }
    }

}
